//
// Created by rebeater on 3/23/21.
//

#ifndef LEETCODE_SORT_H
#define LEETCODE_SORT_H

#include <iostream>
#include <vector>
#include <cmath>

//double nums[]={1,1e1,1e2,1e3,1e4};
void printDouble(double d, uint8_t n);

void sprintDouble(char *buffer, double d, uint8_t n);

namespace rebeater {
class Sort {
 private:
  template<typename T>
  static void insert_sort(std::vector<T> &vector, int n);

  template<typename T>
  static void merge_sort(std::vector<T> &vector, int, int);

//public:
  template<typename T>
  static void merge(std::vector<T> &vector, int, int, int);
  template<class T>
  static void quick_sort(std::vector<T> &vector, int, int);
 public:
  template<typename T>
  static bool check(std::vector<T> &);

  template<typename T>
  static void MergeSort(std::vector<T> &vector);

  template<typename T>
  static void InsertSort(std::vector<T> &vector);

  template<class T>
  static void QuickSort(std::vector<T> &vector);
};

/**
 * 插入排序 复杂度 O(n^2)
 * @tparam T
 * @param vector
 * @param n
 */
template<typename T>
void Sort::insert_sort(std::vector<T> &vector, int n) {
  if (n < 2) {
	return;
  }
  insert_sort(vector, n - 1);
  T key = vector[n - 1]; /*1*/
  int i;
  i = n - 1;
  while (i > 0 and vector[i - 1] > key) {
	vector[i] = vector[i - 1];
	i--;
  }
  vector[i] = key;
/*    std::cout << " key = v[" << n - 1 << "]=" << key << ":";
    for (auto v:vector) std::cout << v << " ";
    std::cout << std::endl;*/
}

template<typename T>
void Sort::InsertSort(std::vector<T> &vector) {
  insert_sort(vector, vector.size());
}

template<typename T>
void Sort::merge_sort(std::vector<T> &vector, int left, int right) {
  if (left < right) {
	int mid = (left + right) / 2;
	merge_sort(vector, left, mid);/*对左边归并排序*/
	merge_sort(vector, mid + 1, right);/*对右边归并排序*/
	merge(vector, left, mid, right);/*合并左右分支*/
  } else
	return;
}

/*归并排序*/
template<typename T>
void Sort::merge(std::vector<T> &vector, int left, int mid, int right) {
  int l_idx = left, r_idx = mid + 1;
  static std::vector<T> temp;
  temp.reserve(vector.size());
  int idx = left;
  while (idx <= right and l_idx <= mid and r_idx <= right) {
	if (vector[l_idx] < vector[r_idx]) {
	  temp[idx] = vector[l_idx];
	  l_idx++;
	} else {
	  temp[idx] = vector[r_idx];
	  r_idx++;
	}
	idx++;
  }
  if (l_idx <= mid) {
	for (int i = l_idx; i <= mid; i++) {
	  temp[idx++] = vector[i];
	}
  }
  if (r_idx <= right) {
	for (int i = r_idx; i <= right; i++) {
	  temp[idx++] = vector[i];
	}
  }
  for (int i = left; i <= right; i++) {
	vector[i] = temp[i];
  }
}

template<typename T>
void Sort::MergeSort(std::vector<T> &vector) {
  merge_sort(vector, 0, vector.size() - 1);
}

template<typename T>
bool Sort::check(std::vector<T> &vector) {
  for (int i = 0; i < vector.size() - 1; i++) {
	if (vector[i] > vector[i + 1]) {
	  return false;
	}
  }
  return true;
}

template<class T>
void Sort::quick_sort(std::vector<T> &array, int low, int high) {
  int i = low, j = high;
  T pivot;
  if (j > i) {
	pivot = array[i];
	while (i != j) {
	  while (j > i and array[j] >= pivot) --j;
	  array[i] = array[j];
	  while (i < j and array[i] <= pivot) ++i;
	  array[j] = array[i];
	}
	array[i] = pivot;
	quick_sort(array, low, i - 1);
	quick_sort(array, i + 1, high);
  }
}
/**
 * 快速排序代码
 * @tparam T
 * @param array
 */
template<class T>
void Sort::QuickSort(std::vector<T> &array) {
  quick_sort(array,0,array.size()-1);
}
}
#endif //LEETCODE_SORT_H
